#include "integerarray.h"
#include "jqsort.h"

// grab len bits from n starting at bit start.
// bit 0 is most significant bit
static uint64 GetBits0H
(uint64 n, uint64 start, uint64 len) {
  return (n << start) >> (64 - len); }

// set len bits in *dest.
// the bits to be written are at the low end of source.
// the high bits of source are ignored.
static void SetBits0H
(uint64 *dest, uint64 source, uint64 start, uint64 len) {
  uint64 mask = ((0xFFFFFFFFFFFFFFFFull >> (64-len)) << (64-len-start));
  uint64 current_bits = (*dest) & mask;
  uint64 new_bits = (source << (64-len-start)) & mask;
  __sync_fetch_and_xor(dest, current_bits ^ new_bits);
}



void IntegerArray::Init(uint64 num_integers, uint64 integer_size) {
  CHECK(integer_size <= 64);
  integer_size_ = integer_size;
  num_integers_ = num_integers;
  word_size_ = 
    RoundUpToMultipleOf(integer_size_ * num_integers_, 64) / 64 + 1;
  if (data_owned_) delete [] data_;
  data_ = new uint64[word_size_];
  data_owned_ = true;
  for (uint64 i=0; i<word_size_; i++) data_[i] = 0;
}

void IntegerArray::Load(Memblock m) {
  const char * p = m.data_;
  Read(&p, &num_integers_);
  Read(&p, &integer_size_);
  if (data_owned_) delete [] data_;
  data_owned_ = false;
  data_ = (uint64 *)p;
}
void IntegerArray::Write(ostream *output) {
  ::Write(output, num_integers_);
  ::Write(output, integer_size_);
  output->write((char *)data_, word_size_ * 8);
}

uint64 IntegerArray::Get(uint64 i) {
  uint64 global_start_bit = i * integer_size_;
  uint64 start_word = global_start_bit >> 6;
  uint64 start_bit = global_start_bit & 0x3F;
  uint64 end_bit = start_bit + integer_size_;
  
  if (end_bit <= 64) { // all in one word
    return GetBits0H(data_[start_word], start_bit, integer_size_);
  } else {
    return 
      (GetBits0H(data_[start_word], start_bit, 64-start_bit) << (end_bit - 64))
      | 
      (GetBits0H(data_[start_word+1], 0, integer_size_ - (64 - start_bit)));
  }
}

void IntegerArray::Set(uint64 i, uint64 val) {
  uint64 global_start_bit = i * integer_size_;
  uint64 start_word = global_start_bit >> 6;
  uint64 start_bit = global_start_bit & 0x3F;
  uint64 end_bit = start_bit + integer_size_;
  
  if (end_bit <= 64) { // all in one word
    SetBits0H(&data_[start_word], val, start_bit, integer_size_);
  } else {
    SetBits0H(&data_[start_word], val >> (end_bit - 64), 
	    start_bit, 64 - start_bit);
    SetBits0H(&data_[start_word+1], val, 0, end_bit - 64);
  }
}

IntegerArray::Reference IntegerArray::GetRef(uint64 i) {
  return (*this)[i];
}

int integerarray_sort_test() {
  uint64 size = 100000000;
  uint64 bits = 34;  
  IntegerArray a;
  a.Init(size, bits);
  for (uint64 i=0; i<size; i++) {
    uint64 j = (i * 209393) % size;
    a[i] = j;
  }
  less<uint64> comp;
  InitJobQueue();
  cout << "ready to sort" << endl;
  JQSort<IntegerArray::iterator, uint64, less<uint64> >
    (a.begin(), a.end(), &comp, G_JQ);
  
  // sort(a.begin(), a.end(), less<uint64>());
  cout << "verifying" << endl;

  for (uint64 i=0; i+1<size; i++) CHECK(a[i] == i);
  cout << "success" << endl;
  return 0;
}

int integerarray_main() {
  return integerarray_sort_test();
}

/*
void IntegerArray::ConvertAndStream
(ostream *output, 
 uint64 *data, 
 uint64 num_integers, 
 uint64 integer_size) {
  ::Write(output, num_integers);
  ::Write(output, integer_size);
  IntegerArray a;
  a.Init(64, integer_size);
  uint64 start = 0;
  for (; start + 64 <= num_integers; start += 64) {
    // these blocks have aligned ends.
    for (uint64 i=0; i<64; i++) a.Set(i, data[start+i]);
    output->write((char *)a.data_, 8 * integer_size);
  }
  a.Init(num_integers-start, integer_size);
  for (uint64 i=start; i<integer_size; i++) a.Set(i-start, data[i]);
  output->write((char*)a.data_, a.word_size_ * 8);
}
*/
